<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="libman.css">
<TITLE>
Approximate Generalised Propagation
</TITLE>
</HEAD>
<BODY >
<A HREF="libman040.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman038.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc78">7.3</A>&nbsp;&nbsp;Approximate Generalised Propagation</H2>
<A NAME="approx"></A>
<A NAME="@default210"></A>
<A NAME="@default211"></A>
<A NAME="@default212"></A>
The syntax <EM>Goal infers most</EM> can also be varied to invoke
different levels of Generalised Propagation. Other alternatives are
<EM>Goal infers ic</EM>, 
<EM>Goal infers unique</EM>, and <EM>Goal infers consistent</EM>.
The strongest constraint is generated by <EM>Goal infers most</EM>,
but it can be expensive to compute. The other alternatives may be
evaluated more efficiently, and may yield a better overall performance
on different applications.
We call them &#8220;approximations&#8221;, since the information they produce
during propagation is a (weaker) approximation of the information
produced by the strongest constraint.<BR>
<BR>
We illustrate the different approximations supported by the current
version of Propia on a single small example.
The results for <EM>Goal infers most</EM> reflect the problem that
structured terms cannot appear in <CODE>IC</CODE> integer domains.
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim"> 
p(1,a).
p(2,f(Z)).
p(3,3).
</PRE>
<PRE CLASS="verbatim">
?- p(X, Y) infers most.
X = X{1 .. 3}
Y = Y
There is 1 delayed goal.
Yes (0.00s cpu)

?- X :: 1 .. 3, p(X, Y) infers most.
X = X{1 .. 3}
Y = Y
There is 1 delayed goal.
Yes (0.00s cpu)

?- p(2, Y) infers most.
Y = f(_326)
There is 1 delayed goal.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE> 
The first approximation we will introduce in this section 
is one that searches for the unique answer to
the query.
It is written <EM>Goal infers unique</EM>.
This is cheap because as soon as two different answers to the query
have been found, the constraint evaluation terminates and the
constraint is delayed again until new information becomes available.
Here are two examples of this approximation.
In the first example notice that no domain is produced for <EM>X</EM>.
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
?- p(X, Y) infers unique.
X = X
Y = Y
There is 1 delayed goal.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
In the second example, by contrast, <CODE>infers unique</CODE> yields the same
result as <CODE>infers most</CODE>: 
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim"> 
?- p(X,X) infers unique.
X = 3
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
The next example shows that <EM>unique</EM> can even capture
nonground answers:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
?- p(2, X) infers unique.
X = f(Z)
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
The next approximation we shall describe is even weaker: it tests if there is an
answer and if not it fails.
If there is an answer it checks to see if the constraint is already
true.
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
?- p(1, X) infers consistent.
X = X
There is 1 delayed goal.
Yes (0.00s cpu)

?- p(1, a) infers consistent.
Yes (0.00s cpu)

?- p(1, X) infers consistent, X = b.
No (0.00s cpu)
</PRE></BLOCKQUOTE>
The strongest language <CODE>infers most</CODE> extracts any information
possible from the loaded constraint solvers. The solvers currently
handled by Propia are <EM>unification</EM> (which is the built-in solver
of Prolog), <EM>ic</EM> and <EM>ic_symbolic</EM>. The <CODE>IC</CODE> library is
loaded by <CODE>lib(ic)</CODE> and the symbolic library by
<CODE>lib(ic_symbolic)</CODE>. These libraries are described elsewhere. If
both libraries are loaded, then <CODE>infers most</CODE> extracts
information from unification, <CODE>IC</CODE> domains and symbolic domains. For example:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim"> 
 p(f(X),1) :- X *&gt;=0, X *=&lt; 10.
 p(f(X),1) :- X=12.
</PRE></BLOCKQUOTE>
with the above program
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim"> 
?- p(X, Y) infers most.
X = f(_338{0.0 .. 12.0})
Y = Y{[1, 2]}
There is 1 delayed goal.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
The approximation <CODE>infers ic</CODE> is
similar to <CODE>infers most</CODE>. However, while <CODE>infers most</CODE>
extracts information based on whatever constraint solvers are loaded, 
the others only infers information derived from the specified constraint
solver.
Here's the same example using <CODE>infers ic</CODE>:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim"> 
?- p(X, Y) infers ic.
X = f(_353{0.0 .. 12.0})
Y = Y{[1, 2]}
There is 1 delayed goal.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
One rather special approximation langue is <CODE>infers ac</CODE>, where
<CODE>ac</CODE> stands for arc-consistency.
This has similar semantics to <CODE>infers ic</CODE>, but is implemented
very efficiently using the built-in <CODE>element</CODE> constraint of the
<CODE>IC</CODE> solver.
The limitation is that <CODE>Goal infers ac</CODE> is implemented by
executing the goal repeatedly to find all the solutions, and then
manipulating the complete set of solutions.
It will only work in case there are finitely many solutions and they
are all ground. <BR>
<BR>
Finally it is possible to invoke Propia in such a way as to influence
its waking conditions. To do this, use the standard
<CODE>suspend</CODE> syntax. For example &#8220;forward checking&#8221; can be
implemented as follows:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
propagate(Goal,fc) :- !,
    suspend(Goal,7,Goal-&gt;inst) infers most.
</PRE></BLOCKQUOTE>
In this case the Propia constraint wakes up each time a variable in
the goal is instantiated. <BR>
<BR>
The default priority for
Propia constraints is 3.
However, in the above example, the priority of the Propia
constraint has been set to 7.<BR>
<BR>
<HR>
<A HREF="libman040.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman038.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
</BODY>
</HTML>
